алгоритмическая сводимость

Игры ⚽ Поможем сделать НИР

АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ — одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, что неразрешимость (и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, а путем сведения к исследуемой проблеме такой … Математическая энциклопедия
НЕРАЗРЕШИМОСТИ СТЕПЕНЬ — класс эквивалентности , индуцированной отношением тьюринговой сводимости на подмножествах натурального ряда ( , если ). Иначе говоря, два множества принадлежат одной Н. с, если для каждого из них существует эффективная разрешающая процедура при… … Математическая энциклопедия

Словари и энциклопедии на Академике